package P70;

import org.junit.Test;

/**
 * @Author DJ同学
 * @Date 2021/2/22 8:49
 * @Version 1.0
 * @Name 爬楼梯
 * @Problem https://leetcode-cn.com/problems/climbing-stairs/
 * @Idea
 *  爬i层楼梯方法数=爬i-1层楼梯方法数+爬i-2层楼梯方法数
 *  dp[0]=0;dp[1]=1;dp[i]=dp[i-1]+dp[i-2]
 *  斐波那契 动态规划
 */
public class Solution {
    @Test
    public void test(){
        System.out.println(climbStairs(4));
    }

    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        int dp1=1;//剩余一级台阶1种方法
        int dp2=2;//剩余二级台阶2种
        int dp=3;
        for(int i=3;i<=n;i++){
            dp=dp1+dp2;
            dp1=dp2;
            dp2=dp;
            //System.out.println(dp);
        }
        return dp;
    }


}
